|
In graph theory, an interval graph is the intersection graph of a family of intervals on the real line. It has one vertex for each interval in the family, and an edge between every pair of vertices corresponding to intervals that intersect. ==Definition== Formally, an interval graph is an undirected graph formed from a family of intervals :''S''''i'', ''i'' = 0, 1, 2, ... by creating one vertex ''v''''i'' for each interval ''S''''i'', and connecting two vertices ''v''''i'' and ''v''''j'' by an edge whenever the corresponding two sets have a nonempty intersection, that is, :''E''(''G'') = From this construction one can verify a common property held by all interval graphs. That is, graph ''G'' is an interval graph if and only if the maximal cliques of ''G'' can be ordered ''M''1, ''M''2, ..., ''M''''k'' such that for any ''v'' ∈ ''M''''i'' ∩ ''M''''k'', where ''i'' < ''k'', it is also the case that ''v'' ∈ ''M''''j'' for any ''M''''j'', ''i'' ≤ ''j'' ≤ ''k''.〔}〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Interval graph」の詳細全文を読む スポンサード リンク
|